#include <climits>
#include <string>
#include <vector>
#include <utility>
#include <algorithm>

using namespace std;

// 1863. 找出所有子集的异或总和再求和
// https://leetcode.cn/problems/sum-of-all-subset-xor-totals/description/
class Solution {
public:
    int subsetXORSum(vector<int>& nums) {
        int ans = 0;
        dfs(nums, 0, 0, ans);
        return ans;
    }

    // 方法一
    void dfs(vector<int>& nums, int pos, int xorNum, int& sum)
    {
        sum += xorNum;
        for (int i = pos; i<nums.size(); ++i)
        {
            dfs(nums, i+1, xorNum ^ nums[i], sum);
        }
    }

    // 方法二
    void dfs(vector<int>& nums, int pos, int xorNum, int& sum)
    {
        if (pos == nums.size())
        {
            sum += xorNum;
            return;
        }

        dfs(nums, pos+1, xorNum^nums[pos], sum);
        dfs(nums, pos+1, xorNum, sum);
    }
};

// leetcode: 47. 全排列 II
// https://leetcode.cn/problems/permutations-ii/
class Solution {
    bool check[8];
    vector<int> path;
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> ans;
        dfs(nums, ans);
        return ans;
    }

    void dfs(vector<int>& nums, vector<vector<int>>& ans)
    {
        if (path.size() == nums.size())
        {
            ans.push_back(path);
            return;
        }

        for (int i = 0; i<nums.size(); ++i)
        {
            if (!check[i] && (i==0 || nums[i]!=nums[i-1] || check[i-1]))
            {
                path.push_back(nums[i]);
                check[i] = true;
                dfs(nums, ans);
                check[i] = false;
                path.pop_back();
            }
        }
    }
};

// 17. 电话号码的字母组合
// https://leetcode.cn/problems/letter-combinations-of-a-phone-number/
class Solution {
    string path;
public:
    vector<string> letterCombinations(string digits) {
        if (digits.size() == 0) return {};
        vector<string> hash( {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"} );
        vector<string> ans;
        dfs(digits, 0, ans, hash);
        return ans;
    }

    void dfs(string& digits, int pos, vector<string>& ans, vector<string>& hash)
    {
        if (path.size() == digits.size())
        {
            ans.push_back(path);
            return;
        }

        for (auto ch : hash[digits[pos]-'0'])
        {
            path.push_back(ch);
            dfs(digits, pos+1, ans, hash);
            path.pop_back();
        }
    }
};

// 22. 括号生成
// https://leetcode.cn/problems/generate-parentheses/
class Solution {
    int left, ritgt;
    string path;
public:
    vector<string> generateParenthesis(int n) {
        left = 0, ritgt = 0;
        vector<string> ans;
        dfs(ans, n);
        return ans;
    }
    
    void dfs(vector<string>& ans, int n)
    {
        if (left < ritgt) return;
        if (ritgt == n)
        {
            ans.push_back(path);
            return;
        }

        if (left < n)
        {
            path.push_back('(');
            ++left;
            dfs(ans, n);
            path.pop_back();
            --left;
        }
        if (ritgt < left)
        {
            path.push_back(')');
            ++ritgt;
            dfs(ans, n);
            path.pop_back();
            --ritgt;
        }
    }
};